/**
 * Created by L.jp
 * Description:
 * 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。
 * User: 86189
 * Date: 2022-03-23
 * Time: 18:35
 */
public class Solution {
    /*如n=1时，只有1中情况，n=2时，有（11,2）两种情况，
    n=3时，有（111,12,21,3）4中情况，当n=4时，有（121,211,112,22,13,31,4,1111）8种情况，因此我们可以看出规律就是2的n-1次方。*/
    public static  int jumpFloorII(int target) {
        //根据推导出的规律就是f(n)=2^(n-1)
        //这个可以利用位运算来求解
        return 1<<--target;  //target先减一，然后再左移target-1位就是次幂的结果

    }

    public static void main(String[] args) {
        System.out.println(jumpFloorII(18));
    }
}
